1. Field of the Invention
The present invention relates to computer memory management methods and apparatus for translating between a virtual address and a physical address stored in a plurality of pages in main memory.
2. Description of Related Art
A computer typically includes main memory and secondary memory. A microprocessor may be included to control the writing and reading of these memory elements. Main memory, constructed of RAM (Random Access Memory) chips is much faster than secondary memory such as a hard disk drive, but main memory is typically much more expensive per memory element. Thus, computers are usually designed with a main memory limited in size and a much larger secondary memory. Microprocessors designed to use virtual memory effectively extend main memory space into secondary memory space. Typically, virtual memory microprocessors use techniques such as paging or segmentation, or both, to simulate a larger memory.
Virtual memory provides many advantages. It is possible to run applications that require more RAM (Random Access Memory) than is actually available. Furthermore, it is possible for more than one application to run at the same time. Virtual memory gives an applications programmer a view of more main memory than actually exists. To a programmer, virtual memory appears as one contiguous block of main memory. An applications programmer seeking storage space does not have to concern himself with the actual physical location of that data, whether the data it be in main memory, or on a hard disk.
In virtual memory systems, the term "physical memory" is used to define the physical address space seen by the operating system. Thus, the size of the physical address space will often be larger than the main memory available in the system. However, the data at any specific physical address must be accessed within the main memory. In operation of virtual memory systems, if requested data is not in main memory, then an operating system exception will be generated and the data will be transferred from secondary storage to main memory under the auspices of the operating system. If paging has been implemented, then a page validity bit may be associated with each page to indicate whether or not the page is in main memory. If the page validity bit indicates that a requested page is not in main memory, then the data is transferred to main memory and the page validity bit is set to indicate that the page is now in main memory.
Virtual memory systems can be categorized into two types: those with variable sized blocks, called "segments", and those with fixed size blocks, called "pages". One, or a combination of these two different methods are used to translate from a virtual address to a physical address. Using segmentation, a block of physical memory is allocated based on the amount of data to be stored. Thus, in a segmented memory structure, one segment may be large and the next may be very small. Segmentation uses memory efficiently, however there are disadvantages. Problems arise when a segmented data structure is modified to be larger. The smaller block must be replaced, and a new, larger block must be found. This problem is substantial, particularly when it is recognized that data structures are often modified.
Paging is the other method for translating a virtual address to a physical address. Pages are fixed size blocks of memory that are mapped in specific locations in physical memory. A "page" is what the programmer sees (part of the logical or linear address), and the "page frame" is the physical memory itself. One or more tables are provided, each of which has a number of page table entries. Each page table entry specifies a specific page frame. The virtual address includes information that is indicative of the table and the page frame.
The use of pages provides advantages. Paging is generally efficient; there are no unused blocks but internal fragmentation (i.e., an unused portion of a page) can be a problem. Replacing a block is trivial. If data is modified to include additional information, then additional pages can be employed. From a design point of view, paging is generally preferred for bigger systems because paging makes allocation of memory easier.
The page size is an important architectural parameter. Choosing a page size is a question of balancing forces that favor a larger page size versus those favoring a smaller size. Advantages of larger page size include memory resources that are saved by use of larger page size, and efficient transfer of larger pages to and from secondary storage. Particularly, memory resources are saved because the size of the page table is inversely proportional to the page size, and thus a larger page size means a smaller table. Also, transferring larger pages is more efficient than transferring smaller pages. For example, the page size for the Intel 80386 and the i486.TM. microprocessor is 4 Kbytes.
Most microprocessors employ a combination of segmentation and paging; specifically, each segment includes a number of pages. This approach to memory management is termed "paged segmentation". Such a system is disclosed in U.S. Pat. No. 4,972,338, entitled "Memory Management For Microprocessor System" issued to Crawford et al., which discloses a segmentation mechanism for translating a virtual memory address to a second memory address (linear address) that is applied to a two-level paging table to select a page frame. The Crawford et al. invention is embodied in the Intel 80386 microprocessor.
Briefly, as described in the Crawford et al. patent, segmentation translates a 48-bit virtual address to a 32-bit linear (intermediate) address. The virtual address includes a segment selector (14 bits) and segment offset (32 bits). Segment offset is the calculated result of the address calculation: scale index and the displacement. The segment selector comes from the segment register. The application programmer must specify a segment register and other components that give the offset. Most applications use only one segment.
FIG. 1 is an illustration of page translation in Intel 80386 microprocessor and the Intel i486.TM. microprocessor. A linear address including a page directory field, a page table field, and an offset field are applied to obtain an operand in a page frame. Within the computer memory, the data structures include page directories, page tables, and page frames. In operation, a page directory in memory is first chosen by a control register CR3. In the linear address, the page directory field selects a page directory entry that specifies a page table in physical memory. The page table field of the linear address selects a page table entry that specifies a page frame of data in physical memory. The offset field of the linear address is applied to select an operand within the page frame. Thus, page translation for the Intel i486.TM. uses a tree structure with two levels of tables in memory.
Each of the tables occupies a 4 Kbyte block of physical memory and each entry is 4 bytes. Therefore each page directory address table has 1K 4-byte entries. The directory field of the linear address is a 10-bit index that selects one of the 1K entries in memory. Similarly, the page table has 1K 4-byte entries that are selected by the 10-bit page table field of the linear address. The 12-bit offset field of the linear address is applied directly to select any operand in the 4K bytes in the page frame. The page frame address is 20 bits in memory. With the 12 bit offset of the linear address, the translation provides a 32-bit physical address, which can access up to 4 Gbytes of physical memory.
Although large by past standards, a 4 Gbyte limit on physical memory is becoming a limitation, particularly for very large servers. For example, banking databases that store customer information may require tens of Gbytes. It would be an advantage to provide a memory management system that is compatible with 32-bit existing software for the 386 and i486.TM., and can access more than 4 Gbytes, for example up to 64 bits (1.8.times.10.sup.10 Gbytes). It would be a performance advantage if the memory access to this larger physical memory could be completed in the same, or a lesser amount of time. It would be another advantage if more than one page size could be selected to choose a page size corresponding to an efficient memory structure for a particular application program or type of data structure.